{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Get Kth Magic Number LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #math #dynamic-programming #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #数学 #动态规划 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getKthMagicNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 k 个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>k = 5\n",
    "\n",
    "<strong>输出: </strong>9\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [get-kth-magic-number-lcci](https://leetcode.cn/problems/get-kth-magic-number-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [get-kth-magic-number-lcci](https://leetcode.cn/problems/get-kth-magic-number-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        f = [0] * (k+1)\n",
    "        f[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "        for i in range(2, k+1):\n",
    "            f[i] = min(f[p3] * 3, f[p5] * 5, f[p7] * 7)\n",
    "            if f[i] == f[p3] * 3:\n",
    "                p3 += 1\n",
    "            if f[i] == f[p5] * 5:\n",
    "                p5 += 1\n",
    "            if f[i] == f[p7] * 7:\n",
    "                p7 += 1\n",
    "        return f[k] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors=[3,5,7]\n",
    "        seen={1}\n",
    "        heap=[1]\n",
    "        for i in range(k-1):\n",
    "            curr=heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt:=curr*factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap,nxt)\n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "\n",
    "        return dp[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        heap_list = []\n",
    "        heapq.heappush(heap_list,1)\n",
    "        heapq.heappush(heap_list,3)\n",
    "        heapq.heappush(heap_list,5)\n",
    "        heapq.heappush(heap_list,7)\n",
    "        heapq.heappush(heap_list,9)\n",
    "        heapq.heappush(heap_list,15)\n",
    "        heapq.heappush(heap_list,21)\n",
    "        visited_set = set([1,3,5,7,9,15,21])\n",
    "        rs = 0\n",
    "        for i in range(k):\n",
    "            rs = heapq.heappop(heap_list)\n",
    "            if rs*3 not in visited_set:\n",
    "                heapq.heappush(heap_list,rs*3)\n",
    "                visited_set.add(rs*3)\n",
    "            if rs*5 not in visited_set:\n",
    "                heapq.heappush(heap_list,rs*5)\n",
    "                visited_set.add(rs*5)\n",
    "            if rs*7 not in visited_set:\n",
    "                heapq.heappush(heap_list,rs*7)\n",
    "                visited_set.add(rs*7)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3, 5, 7]\n",
    "        minheap = [1]   # first node in min-heap is 1\n",
    "\n",
    "        for _ in range(k):\n",
    "            curr = heappop(minheap)\n",
    "            for factor in factors:\n",
    "                heappush(minheap, curr*factor)\n",
    "                if curr % factor == 0:\n",
    "                    break\n",
    "\n",
    "        return curr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        ans, pq = 0, [1]\n",
    "        factors = [3, 5, 7]\n",
    "        while k:\n",
    "            cur = heapq.heappop(pq)\n",
    "            if ans < cur:\n",
    "                ans = cur\n",
    "                k -= 1\n",
    "                for p in factors:\n",
    "                    heapq.heappush(pq, p*cur)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        k_3, k_5, k_7 = 0, 0, 0\n",
    "        arr = [1]\n",
    "        while len(arr) < k:\n",
    "            op = '3'\n",
    "            next = arr[k_3] * 3\n",
    "            if arr[k_5] * 5 < next:\n",
    "                op = '5'\n",
    "                next = arr[k_5] * 5\n",
    "            if arr[k_7] * 7 < next:\n",
    "                op = '7'\n",
    "                next = arr[k_7] * 7\n",
    "\n",
    "            if op == '3':\n",
    "                if arr[k_3] * 3 not in arr:\n",
    "                    arr.append(arr[k_3] * 3)\n",
    "                k_3 += 1\n",
    "            elif op == '5':\n",
    "                if arr[k_5] * 5 not in arr:\n",
    "                    arr.append(arr[k_5] * 5)\n",
    "                k_5 += 1\n",
    "            else:\n",
    "                if arr[k_7] * 7 not in arr:\n",
    "                    arr.append(arr[k_7] * 7)\n",
    "                k_7 += 1\n",
    "        return arr[k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        res = [1]\n",
    "        id3, id5, id7 = 0, 0, 0\n",
    "        for i in range(1, k):\n",
    "            value = min(min(res[id3]*3, res[id5]*5), res[id7]*7)\n",
    "            if value == res[id3]*3:\n",
    "                id3 += 1\n",
    "            if value == res[id5]*5:\n",
    "                id5 += 1\n",
    "            if value == res[id7]*7:\n",
    "                id7 += 1\n",
    "            res.append(value)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3, 5, 7]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(k - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        if k<=7:\n",
    "            res=[1,3,5,7,9,15,21]\n",
    "            return res[k-1]\n",
    "        res={1,3,5,7,9,15,21}\n",
    "        count=0\n",
    "        while count+1<k:\n",
    "            minnum=min(list(res))\n",
    "            res.add(minnum*3)\n",
    "            res.add(minnum*5)\n",
    "            res.add(minnum*7)\n",
    "            res.remove(minnum)\n",
    "            count+=1\n",
    "        return min(list(res))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        res = [1]\n",
    "        a = b = c = 0\n",
    "        while len(res) < k:\n",
    "            res.append(min(res[a]*3, res[b]*5, res[c]*7))\n",
    "            if res[-1] == res[a]*3:    a+=1\n",
    "            if res[-1] == res[b]*5:    b+=1\n",
    "            if res[-1] == res[c]*7:    c+=1\n",
    "            \n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp=[1]*(k+1)\n",
    "        p3,p5,p7=1,1,1\n",
    "        for i in range(2,k+1):\n",
    "            dp[i]=min(dp[p3]*3,dp[p5]*5,dp[p7]*7)\n",
    "            if dp[i]==dp[p3]*3: p3+=1\n",
    "            if dp[i]==dp[p5]*5: p5+=1\n",
    "            if dp[i]==dp[p7]*7: p7+=1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [1] * (k+1)\n",
    "        p3, p5, p7 = 1, 1, 1\n",
    "        for i in range(2, k+1):\n",
    "            a, b, c = 3*dp[p3], 5*dp[p5], 7*dp[p7]\n",
    "            v = min(a, b, c)\n",
    "            dp[i] = v\n",
    "            if a == v:\n",
    "                p3 += 1\n",
    "            if b == v:\n",
    "                p5 += 1\n",
    "            if c == v:\n",
    "                p7 += 1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        # 动态规划\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "        \n",
    "        return dp[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        nums = [1]\n",
    "        i3,i5,i7 = 0,0,0\n",
    "        while len(nums) < k:\n",
    "            n3 = nums[i3]*3\n",
    "            n5 = nums[i5]*5\n",
    "            n7 = nums[i7]*7\n",
    "            n = min(n3,n5,n7)\n",
    "            nums.append(n)\n",
    "            if n3 == n:\n",
    "                i3 += 1\n",
    "            if n5 == n:\n",
    "                i5 += 1\n",
    "            if n7 == n:\n",
    "                i7 += 1\n",
    "        \n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        nums = [1]\n",
    "        p3, p5, p7 = 0, 0, 0\n",
    "        while len(nums) < k:\n",
    "            x3, x5, x7 = nums[p3] * 3, nums[p5] * 5, nums[p7] * 7\n",
    "            x = min(x3, x5, x7)\n",
    "            nums.append(x)\n",
    "            if x == x3:\n",
    "                p3 += 1\n",
    "            if x == x5:\n",
    "                p5 += 1\n",
    "            if x == x7:\n",
    "                p7 += 1\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "        \n",
    "        return dp[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        arr = [1 for _ in range(k+1)]\n",
    "\n",
    "        i3 = i5 = i7 = 1\n",
    "        for i in range(2, k+1):\n",
    "            n1, n2, n3 = arr[i3] * 3, arr[i5] * 5, arr[i7] * 7\n",
    "            num = min(n1, n2, n3)\n",
    "\n",
    "            i3 = i3 + 1 if num == n1 else i3\n",
    "            i5 = i5 + 1 if num == n2 else i5\n",
    "            i7 = i7 + 1 if num == n3 else i7\n",
    "\n",
    "            arr[i] = num\n",
    "        return arr[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp=[0]*(k+1)\n",
    "        dp[1]=1\n",
    "        p3=p5=p7=1\n",
    "        for i in range(2,k+1):\n",
    "            num3,num5,num7=dp[p3]*3,dp[p5]*5,dp[p7]*7\n",
    "            dp[i]=min(num3,num5,num7)\n",
    "            if dp[i]==num3:\n",
    "                p3+=1\n",
    "            if dp[i]==num5:\n",
    "                p5+=1\n",
    "            if dp[i]==num7:\n",
    "                p7+=1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [1] * k\n",
    "        flag_3, flag_5, flag_7  = 0, 0, 0\n",
    "        for i in range(1, k):\n",
    "            dp[i] = min(dp[flag_3] * 3, dp[flag_5] * 5, dp[flag_7] * 7)\n",
    "            if dp[i] == dp[flag_3] * 3:\n",
    "                flag_3 += 1\n",
    "            if dp[i] == dp[flag_5] * 5:\n",
    "                flag_5 += 1\n",
    "            if dp[i] == dp[flag_7] * 7:\n",
    "                flag_7 += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        heap = []\n",
    "        heapq.heappush(heap,1)\n",
    "        book = set()\n",
    "        book.add(1)\n",
    "        cnt = 0\n",
    "        while(heapq):\n",
    "            num = heapq.heappop(heap)\n",
    "            cnt += 1\n",
    "            if(cnt == k):\n",
    "                return num \n",
    "            for i in [3,5,7]:\n",
    "                if(i*num not in book):\n",
    "                    book.add(i*num)\n",
    "                    heapq.heappush(heap,i*num)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "factor=[3,5,7]\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        # h=[1]\n",
    "        # vis={1}\n",
    "        # for _ in range(k-1):\n",
    "        #     cur=heapq.heappop(h)\n",
    "        #     for i in factor:\n",
    "        #         if i*cur not in vis:\n",
    "        #             heapq.heappush(h,i*cur)\n",
    "        #             vis.add(i*cur)\n",
    "        # return h[0]\n",
    "        dp=[1]*(k+1)\n",
    "        p3=p5=p7=1\n",
    "        for i in range(2,k+1):\n",
    "            a,b,c=dp[p3]*3,dp[p5]*5,dp[p7]*7\n",
    "            v=min(a,b,c)\n",
    "            dp[i]=v\n",
    "            if v==a:\n",
    "                p3+=1\n",
    "            if v==b:\n",
    "                p5+=1\n",
    "            if v==c:\n",
    "                p7+=1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "\n",
    "        heap = [1]\n",
    "        coll = []\n",
    "\n",
    "        for i in range(k - 1):\n",
    "\n",
    "            mini = heapq.heappop(heap)\n",
    "            while mini in coll:\n",
    "                mini = heapq.heappop(heap)\n",
    "            coll.append(mini)\n",
    "\n",
    "\n",
    "            heap.append(mini * 3)\n",
    "            heap.append(mini * 5)\n",
    "            heap.append(mini * 7)\n",
    "            heapq.heapify(heap)\n",
    "\n",
    "        mini = heapq.heappop(heap)\n",
    "        while mini in coll:\n",
    "            mini = heapq.heappop(heap)\n",
    "\n",
    "        return mini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        q = [1]\n",
    "        for i in range(k-1):\n",
    "            cur = heapq.heappop(q)\n",
    "            for j in (3,5,7):\n",
    "                value = j*cur\n",
    "                if value not in q:\n",
    "                    heapq.heappush(q,value)\n",
    "        return heapq.heappop(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3,5,7]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "        for i in range(k-1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt:=curr*factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap,nxt)\n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp=[0]*(k+1)\n",
    "        dp[1]=1\n",
    "        p3=p5=p7=1\n",
    "        for i in range(2,k+1):\n",
    "            num3,num5,num7=dp[p3]*3,dp[p5]*5,dp[p7]*7\n",
    "            dp[i]=min(num3,num5,num7)\n",
    "            if dp[i]==num3:\n",
    "                p3+=1\n",
    "            if dp[i]==num5:\n",
    "                p5+=1\n",
    "            if dp[i]==num7:\n",
    "                p7+=1\n",
    "        return dp[k]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        data = [1]\n",
    "        vis = {1}\n",
    "        for i in range(k):\n",
    "            cur = heapq.heappop(data)\n",
    "            for m in [3,5,7]:\n",
    "                if cur*m not in vis:\n",
    "                    vis.add(cur*m)\n",
    "                    heapq.heappush(data,cur*m)\n",
    "\n",
    "\n",
    "\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "\n",
    "        heap = [1]\n",
    "        coll = []\n",
    "\n",
    "        for i in range(k - 1):\n",
    "\n",
    "            mini = heapq.heappop(heap)\n",
    "            while mini in coll:\n",
    "                mini = heapq.heappop(heap)\n",
    "            coll.append(mini)\n",
    "\n",
    "\n",
    "            heapq.heappush(heap,mini * 3)\n",
    "            heapq.heappush(heap,mini * 5)\n",
    "            heapq.heappush(heap,mini * 7)\n",
    "\n",
    "            \n",
    "\n",
    "        mini = heapq.heappop(heap)\n",
    "        while mini in coll:\n",
    "            mini = heapq.heappop(heap)\n",
    "\n",
    "        return mini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        pos = [0]*3\n",
    "        ret = [1]\n",
    "        for _ in range(k-1):\n",
    "            arr = [ret[pos[0]]*3, ret[pos[1]]*5, ret[pos[2]]*7]\n",
    "            nxt = min(arr)\n",
    "            if nxt == arr[0]:\n",
    "                pos[0] += 1\n",
    "            if nxt == arr[1]:\n",
    "                pos[1] += 1\n",
    "            if nxt == arr[2]:\n",
    "                pos[2] += 1\n",
    "            ret.append(nxt)\n",
    "        return ret[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        if k<=4:\n",
    "            return k*2-1\n",
    "        # 1 3 5 7 9 15 21 25\n",
    "        dp=[1 for i in range(k+1)]\n",
    "        dp[1]=1\n",
    "        p1,p2,p3=1,1,1\n",
    "        for i in range(2,k+1):\n",
    "            num1,num2,num3 = dp[p1]*3,dp[p2]*5,dp[p3]*7\n",
    "            dp[i]=min(num1,num2,num3)\n",
    "            if dp[i]==num1:\n",
    "                p1+=1\n",
    "            if dp[i]==num2:\n",
    "                p2+=1\n",
    "            if dp[i]==num3:\n",
    "                p3+=1\n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3, 5, 7]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(k - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "        \n",
    "        return dp[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        if k < 0:\n",
    "            return \n",
    "        dp = [1]*k\n",
    "        index_3, index_5, index_7 = 0, 0, 0\n",
    "        for i in range(1,k):            \n",
    "            dp[i] = min(dp[index_7]*7, dp[index_3]*3, dp[index_5]*5)\n",
    "            if dp[i] == dp[index_7]*7:\n",
    "                index_7 += 1\n",
    "            if dp[i] == dp[index_3]*3:\n",
    "                index_3 += 1\n",
    "            if dp[i] == dp[index_5]*5:\n",
    "                index_5 += 1\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "#  和丑数2是一道题目"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        base_heap = []\n",
    "        res = [1]\n",
    "        for b in (3, 5, 7):\n",
    "            heappush(base_heap, (b, b, 0))\n",
    "        for _ in range(k-1):\n",
    "            num, base, i = heappop(base_heap)\n",
    "            res.append(num)\n",
    "            heappush(base_heap, (base*res[i+1], base, i+1))\n",
    "            while base_heap[0][0] == num:\n",
    "                n, b, i = heappop(base_heap)\n",
    "                heappush(base_heap, (b*res[i+1], b, i+1))\n",
    "        return res[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        p3,p5,p7 = 0,0,0\n",
    "        dp = [1]*k\n",
    "        for i in range(1,k):\n",
    "            tmp3,tmp5,tmp7 = 3*dp[p3],5*dp[p5],7*dp[p7]\n",
    "            dp[i] = min(tmp3,tmp5,tmp7)\n",
    "            if dp[i]==tmp3:\n",
    "                p3+=1\n",
    "            if dp[i]==tmp5:\n",
    "                p5+=1\n",
    "            if dp[i]==tmp7:\n",
    "                p7+=1\n",
    "        return dp[-1]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        import heapq\n",
    "\n",
    "        numbers = set()\n",
    "        heap = [1]\n",
    "        while(k):\n",
    "            cur = heapq.heappop(heap)\n",
    "            if(cur not in numbers):\n",
    "                k = k - 1\n",
    "                heapq.heappush(heap, cur *3)\n",
    "                heapq.heappush(heap, cur *5)\n",
    "                heapq.heappush(heap, cur *7)\n",
    "                numbers.add(cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "        \n",
    "        return dp[k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef getKthMagicNumber(self, k: int) -> int:\n",
    "\t\tdp = [0] * (k + 1)\n",
    "\t\tdp[1] = 1\n",
    "\t\tp3 = p5 = p7 = 1\n",
    "\n",
    "\t\tfor i in range(2, k + 1):\n",
    "\t\t\tnum3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "\t\t\tdp[i] = min(num3, num5, num7)\n",
    "\t\t\tif dp[i] == num3:\n",
    "\t\t\t\tp3 += 1\n",
    "\t\t\tif dp[i] == num5:\n",
    "\t\t\t\tp5 += 1\n",
    "\t\t\tif dp[i] == num7:\n",
    "\t\t\t\tp7 += 1\n",
    "\n",
    "\t\treturn dp[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        l = j = m = 1\n",
    "        for i in range(2, k + 1):\n",
    "            min3 = dp[l] * 3\n",
    "            min5 = dp[j] * 5\n",
    "            min7 = dp[m] * 7\n",
    "            dp[i] = min(min3, min5, min7)\n",
    "            if dp[i] == min3:\n",
    "                l += 1\n",
    "            if dp[i] == min5:\n",
    "                j += 1\n",
    "            if dp[i] == min7:\n",
    "                m += 1\n",
    "        return dp[k] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        h = [1]\n",
    "        num_set = set([1])\n",
    "        result = -1\n",
    "        for _ in range(k):\n",
    "            result = heapq.heappop(h)\n",
    "            for i in [3, 5, 7]:\n",
    "                temp = result * i\n",
    "                if temp not in num_set:\n",
    "                    num_set.add(temp)\n",
    "                    heapq.heappush(h, temp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        p1,p2,p3=0,0,0\n",
    "        nums=[1]\n",
    "        for _ in range(1,k):\n",
    "            num=min(nums[p1]*3,nums[p2]*5,nums[p3]*7)\n",
    "            if num==nums[p1]*3: p1+=1\n",
    "            if num==nums[p2]*5: p2+=1\n",
    "            if num==nums[p3]*7: p3+=1\n",
    "            nums.append(num)\n",
    "        return nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        p3 = p5 = p7 = 1\n",
    "\n",
    "        for i in range(2, k + 1):\n",
    "            num3, num5, num7 = dp[p3] * 3, dp[p5] * 5, dp[p7] * 7\n",
    "            dp[i] = min(num3, num5, num7)\n",
    "            if dp[i] == num3:\n",
    "                p3 += 1\n",
    "            if dp[i] == num5:\n",
    "                p5 += 1\n",
    "            if dp[i] == num7:\n",
    "                p7 += 1\n",
    "        \n",
    "        return dp[k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "factor=[3,5,7]\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        h=[1]\n",
    "        vis={1}\n",
    "        for _ in range(k-1):\n",
    "            cur=heapq.heappop(h)\n",
    "            for i in factor:\n",
    "                if i*cur not in vis:\n",
    "                    heapq.heappush(h,i*cur)\n",
    "                    vis.add(i*cur)\n",
    "        return h[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3, 5, 7]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(k - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                nxt = curr * factor\n",
    "                if nxt not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp=[1]*(k+1)\n",
    "        p3,p5,p7=1,1,1\n",
    "        for i in range(2,k+1):\n",
    "            num1,num2,num3=dp[p3]*3,dp[p5]*5,dp[p7]*7\n",
    "            dp[i]=min(num1,num2,num3)\n",
    "            if dp[i]==num1: p3+=1\n",
    "            if dp[i]==num2: p5+=1\n",
    "            if dp[i]==num3: p7+=1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp=[1]*(k+1)\n",
    "        p3,p5,p7=1,1,1\n",
    "        for i in range(2,k+1):\n",
    "            num1,num2,num3=dp[p3]*3,dp[p5]*5,dp[p7]*7\n",
    "            dp[i]=min(num1,num2,num3)\n",
    "            if dp[i]==num1: p3+=1\n",
    "            if dp[i]==num2: p5+=1\n",
    "            if dp[i]==num3: p7+=1\n",
    "        return dp[k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factor=[3,5,7]\n",
    "        flag={1}\n",
    "        heap=[1]\n",
    "        for i in range (k):\n",
    "            ans=heappop(heap)\n",
    "            for j in factor:\n",
    "                if ans*j not in flag:\n",
    "                    flag.add(ans*j)\n",
    "                    heappush(heap,ans*j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "        i3, i5, i7 = 1, 1, 1\n",
    "        for i in range(2, k + 1):\n",
    "            res = min(dp[i3] * 3, dp[i5] * 5, dp[i7] * 7)\n",
    "            if res == dp[i3] * 3:\n",
    "                i3 += 1\n",
    "            if res == dp[i5] * 5:\n",
    "                i5 += 1\n",
    "            if res == dp[i7] * 7:\n",
    "                i7 += 1\n",
    "            dp[i] = res\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify, heappush, heappop\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        q = [1]\n",
    "        visited = set()\n",
    "        for _ in range(k):\n",
    "            cur = heappop(q)\n",
    "            for factor in [3, 5, 7]:\n",
    "                guess = factor * cur\n",
    "                if guess not in visited:\n",
    "                    visited.add(guess)\n",
    "                    heappush(q, guess)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        if k==1:\n",
    "            return 1\n",
    "        \n",
    "        time3 = [3]\n",
    "        time5 = [5]\n",
    "        time7 = [7]\n",
    "        p1, p2, p3 = 0, 0, 0\n",
    "        while k>1:\n",
    "            now = min(time3[p1], time5[p2], time7[p3])\n",
    "            if now==time3[p1]:\n",
    "                p1 += 1\n",
    "            if now==time5[p2]:\n",
    "                p2 += 1\n",
    "            if now==time7[p3]:\n",
    "                p3 += 1\n",
    "            \n",
    "            time3.append(now*3)\n",
    "            time5.append(now*5)\n",
    "            time7.append(now*7)\n",
    "\n",
    "            k -= 1\n",
    "            print(now)\n",
    "        \n",
    "        return now\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        p3,p5,p7 = 0,0,0\n",
    "        dp = [1]*k\n",
    "        for i in range(1,k):\n",
    "            tmp3,tmp5,tmp7 = 3*dp[p3],5*dp[p5],7*dp[p7]\n",
    "            dp[i] = min(tmp3,tmp5,tmp7)\n",
    "            if dp[i]==tmp3:\n",
    "                p3+=1\n",
    "            if dp[i]==tmp5:\n",
    "                p5+=1\n",
    "            if dp[i]==tmp7:\n",
    "                p7+=1\n",
    "        return dp[-1]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        hp = [1]\n",
    "        \n",
    "        for i in range(k):\n",
    "            res = heapq.heappop(hp) #最小值\n",
    "            while hp and res == hp[0]:\n",
    "                heapq.heappop(hp)\n",
    "            heapq.heappush(hp, res*3)\n",
    "            heapq.heappush(hp, res*5)\n",
    "            heapq.heappush(hp, res*7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [1 for i in range(k+1)]\n",
    "        p3 = 1\n",
    "        p5 = 1\n",
    "        p7 = 1\n",
    "        for i in range(2,k+1):\n",
    "            mini = min(dp[p3] * 3, dp[p5] * 5, dp[p7] * 7)\n",
    "            dp[i] = mini\n",
    "            if mini == dp[p3] * 3:\n",
    "                p3 += 1\n",
    "            if mini == dp[p5] * 5:\n",
    "                p5 += 1\n",
    "            if mini == dp[p7] * 7:\n",
    "                p7 += 1\n",
    "        return dp[k] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        mem, cur = [1], 1\n",
    "        seen = set([1])\n",
    "        dc = [3, 5, 7]\n",
    "        heapq.heapify(mem)\n",
    "\n",
    "        # 用堆保持顺序性\n",
    "        while len(seen) < k:\n",
    "            cur = heapq.heappop(mem)\n",
    "            for item in dc:\n",
    "                new = item * cur\n",
    "                if new not in mem:\n",
    "                    heapq.heappush(mem, new)\n",
    "            seen.add(cur)\n",
    "        \n",
    "        return cur\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        if k < 0:\n",
    "            return \n",
    "        dp = [1]*k\n",
    "        index_3, index_5, index_7 = 0, 0, 0\n",
    "        for i in range(1,k):            \n",
    "            dp[i] = min(dp[index_7]*7, dp[index_3]*3, dp[index_5]*5)\n",
    "            if dp[i] == dp[index_7]*7:\n",
    "                index_7 += 1\n",
    "            if dp[i] == dp[index_3]*3:\n",
    "                index_3 += 1\n",
    "            if dp[i] == dp[index_5]*5:\n",
    "                index_5 += 1\n",
    "\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        p3,p5,p7 = 0,0,0\n",
    "        dp = [1]*k\n",
    "        for i in range(1,k):\n",
    "            tmp3,tmp5,tmp7 = 3*dp[p3],5*dp[p5],7*dp[p7]\n",
    "            dp[i] = min(tmp3,tmp5,tmp7)\n",
    "            if dp[i]==tmp3:\n",
    "                p3+=1\n",
    "            if dp[i]==tmp5:\n",
    "                p5+=1\n",
    "            if dp[i]==tmp7:\n",
    "                p7+=1\n",
    "        return dp[-1]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        heap = [1]\n",
    "        numbers = set()\n",
    "        # 每次从小顶堆取一个， 取 k 次即可\n",
    "        while k:\n",
    "            cur = heappop(heap)\n",
    "            if cur not in numbers:\n",
    "                k -= 1\n",
    "                heappush(heap, cur * 3)\n",
    "                heappush(heap, cur * 5)\n",
    "                heappush(heap, cur * 7)\n",
    "            numbers.add(cur)\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "1\n",
    "5\n",
    "7\n",
    "\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        dp = [0]*k\n",
    "        dp[0] = 1\n",
    "        i3, i5, i7 = 0,0,0\n",
    "        for i in range(1, k):\n",
    "            dp[i] = min(dp[i3]*3, dp[i5]*5, dp[i7]*7)\n",
    "            if dp[i] == dp[i3]*3:\n",
    "                i3 += 1\n",
    "            if dp[i] == dp[i5]*5:\n",
    "                i5 += 1\n",
    "            if dp[i] == dp[i7]*7:\n",
    "                i7 += 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, n: int) -> int:\n",
    "        # ans 用作存储已有丑数（从下标 1 开始存储，第一个丑数为 1）\n",
    "        ans = [0] * (n+1)\n",
    "        ans[1] = 1\n",
    "        # 由于三个有序序列都是由「已有丑数」*「质因数」而来\n",
    "        # i2、i3 和 i5 分别代表三个有序序列当前使用到哪一位「已有丑数」下标（起始都指向 1）\n",
    "        i2 = i3 = i5 = 1\n",
    "        idx = 2\n",
    "        while idx <= n:\n",
    "            # 由 ans[iX] * X 可得当前有序序列指向哪一位\n",
    "            a,b,c = ans[i2] * 3, ans[i3] * 5,ans[i5]* 7\n",
    "            # 将三个有序序列中的最小一位存入「已有丑数」序列，并将其下标后移\n",
    "            m = min(a,b,c)\n",
    "            # 由于可能不同有序序列之间产生相同丑数，因此只要一样的丑数就跳过（不能使用 else if ）\n",
    "            if m == a:\n",
    "                i2 += 1\n",
    "            if m == b:\n",
    "                i3 += 1\n",
    "            if m == c:\n",
    "                i5 += 1\n",
    "            ans[idx] = m\n",
    "            idx += 1\n",
    "        return ans[n]\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        from queue import PriorityQueue\n",
    "        queue = PriorityQueue()\n",
    "        queue.put(1)\n",
    "\n",
    "        data = 0\n",
    "        mem = set()\n",
    "        while k:\n",
    "            data = queue.get()\n",
    "            if data * 3 not in mem:\n",
    "                queue.put(data * 3)\n",
    "                mem.add(data * 3)\n",
    "            if data * 5 not in mem:\n",
    "                queue.put(data * 5)\n",
    "                mem.add(data * 5)\n",
    "            if data * 7 not in mem:\n",
    "                queue.put(data * 7)\n",
    "                mem.add(data * 7)\n",
    "            k -= 1\n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        # 3 5 7\n",
    "        # 33 9\n",
    "        # 35 15\n",
    "        # 37 21\n",
    "        # 55 25\n",
    "        # 57 35\n",
    "        # 77 49\n",
    "        # 39 27\n",
    "        # 59 45\n",
    "        # 79 63\n",
    "        if k == 1:\n",
    "            return 1\n",
    "        res = [0 for _ in range(k+1)]\n",
    "        res[1] = 1\n",
    "        t, f, s = 1, 1, 1\n",
    "        for i in range(2, len(res)):\n",
    "            mins = min(res[t]*3, res[f]*5, res[s]*7)\n",
    "            if mins == res[t]*3:\n",
    "                t += 1\n",
    "            if mins == res[f]*5:\n",
    "                f += 1\n",
    "            if mins == res[s]*7:\n",
    "                s += 1\n",
    "            res[i] = mins \n",
    "        return res[-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        \n",
    "        # 规律[0, 1, 3, 5, 7, 9, 15, 21, 25, 27,]\n",
    "        # dp[i]：第i个数为dp[i]\n",
    "        dp = [0] * (k + 1)\n",
    "        dp[1] = 1\n",
    "\n",
    "        # 简单一句话说清楚就是，三个指针（p3,p5,p7)分别代表3，5，7，乘某个数所能贡献的最小值(val)，\n",
    "        # 当这个val被用过了，就不会再出现，因此需要将对应的指针位置+1\n",
    "\n",
    "\n",
    "        p3 = p5 = p7 = 1\n",
    "        \n",
    "        for i in range(2, k+1):\n",
    "            n3, n5, n7 = dp[p3]*3, dp[p5]*5, dp[p7]*7\n",
    "            dp[i] = min(n3, n5, n7)\n",
    "\n",
    "            if dp[i] == n3:\n",
    "                p3 += 1\n",
    "            if dp[i] == n5:\n",
    "                p5 += 1\n",
    "            if dp[i] == n7:\n",
    "                p7 += 1\n",
    "\n",
    "        \n",
    "\n",
    "        return dp[k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthMagicNumber(self, k: int) -> int:\n",
    "        factors = [3, 5, 7]\n",
    "        seen = {1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(k - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in factors:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen.add(nxt)\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
